﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;

//因为表中存的数字可能是任何数字，因此不能用数字来标志表中某个位置
//是否已经插入元素，因此用State来标志：
enum State {
	EMPTY,   //位置为空
	DELETE,  //位置的元素已经被删除
	EXIST     //位置存在元素
};
template<class K,class V>
struct HashDate {    //哈希表里存的是一个pair和标志该位置状态的_state
	pair<K, V> _kv;
	State _state=EMPTY;
};
template<class K>
class HashFunc   //普通数据类型用
{
public:
	size_t operator()( const K& key) {  //对于Key是正数,负数,浮点数,只需将它们直接
		return (size_t)(key);           //转化为size_t即可。
	}

};
//特化：（要求与一般模板类名字一样）
template<>
struct HashFunc<string>
{
	// 字符串转换成整形，可以把字符ascii码相加即可
	// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
    // 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131
	//等效果会⽐较好
	size_t operator()(const string& key) {
		size_t hash = 0;
		for (auto num : key) {
			hash += num;
			hash *= 131;
		}
		return hash;
	}
};
template<class K,class V,class HashFunctor=HashFunc<K>>
class Hash {
public:
	Hash() {
		_tables.resize(11);  //这里哈希表大小初始化为11,哈希表的大小尽量取不靠近
		                    //2的幂和10的幂的素数。

	}
	
	bool insert(pair<K,V> kv) {
		if (find(kv.first)) { //已经存在
			return false;
		}
		/*假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么负载因⼦=N/M
		。负载因⼦越⼤，哈希冲突的概率越⾼，空间
		利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低*/

		//对于负载因子，当其大小>=0.7时，表的空间基本快用完了，需要扩容
		//如，已经存储了7个元素，哈希表的大小为10，则负载因子==0.7

		if (n * 10 / _tables.size() >= 7) {  //直接用n/_table.size()>=0.7来判断
			                     //是不行的，如7/10==0 ，如取不了小数点后
			               //的数字 ，可以将其中一个数字转成double类型或者如上面那样写
			
			//扩容： 1.新的哈希表大小扩为原来的2倍+1
			//       2.并将旧的表内的数据存进新的表中
			// 
			// 注意：旧的表内的元素在新的表内的映射位置很大可能发生了改变
			//       要重新映射插入。
			// 
			//这里的将旧元素插入到新表中的机制不需要我们自己重新将旧的表内的_kv
			//取出来然后根据_kv的key%新的表的size,来重新映射到新的
			//表上。  （现代写法）
			Hash<K,V> newhash;
			newhash._tables.resize(_tables.size() * 2 + 1);
			for (auto& num : _tables) {  //遍历旧的表
				if (num._state == EXIST) { 
					newhash.insert(num._kv); //将元素插入到新的表中，这里调用insert函数
					                  //注意：这里不是递归，因为这里调用insert后会直接
					                 //走到下面的寻址并插入的逻辑中，不会满足前面的几个
					             //if条件
				}
			}
			_tables.swap(newhash._tables);  //直接交换两张哈希表，
			                              //旧的表（局部变量）会自动释放
		}

		//寻址并插入：
		HashFunctor func;
		//注意：因为不知道Key是什么类型，因此要用仿函数一致将它们转化为size_t 的整形
		size_t pos0 = func(kv.first) % _tables.size(); 
		                                                
		size_t pos1 = pos0;
		while (_tables[pos1]._state == EXIST) //找空的位置或者被删除的位置
		{
			pos1++;  //往后找 
			pos1 = pos1 % _tables.size();  
		}
		//找到了：插入HashDate：
		_tables[pos1]._kv = kv; 
		_tables[pos1]._state = EXIST;
		++n;  //表内元素个数
		return true;
	}
	HashDate<K, V>* find( const K& key) {

		//注意：因为不知道Key是什么类型，因此要用仿函数一致将它们转化为size_t 的整形：
		HashFunctor func;
		size_t pos = func(key) % _tables.size();

		while (_tables[pos]._state != EMPTY) {  //当走到空的位置该元素一定不存在

			//当该位置的状态为存在并且pair的key与key相等时才是找到了：
			if (_tables[pos]._state == EXIST &&  
				_tables[pos]._kv.first == key) {
				return &_tables[pos];
			}
            //往后遍历：
			pos++;
			pos = pos % _tables.size();
		}
		return nullptr;
	}
	void erase( const K& key) {
		HashDate<K, V>* ret = find(key);
		if (ret) {
			n--; 
			ret->_state = DELETE;
		}
	}
private:
	vector<HashDate<K, V>> _tables;
	size_t n=0;
};
